package com.cty.LinkedList;

//*****重点问题******
public class question05 {
    //合并两个有序的单链表,合并成一个有序链表
    public static SingleLinkedList merge(SingleLinkedList linkedList1, SingleLinkedList linkedList2) {
        //创建一个合并后的单链表
        SingleLinkedList NewSingleLinkedList = new SingleLinkedList();
        //获取第一个单链表的头节点
        heroNode head1 = linkedList1.getHead();
        //获得第二个单链表的头节点
        heroNode head2 = linkedList2.getHead();
        //获得一个新链表的头节点
        heroNode head3 = NewSingleLinkedList.getHead();
        //判断两个链表是否为空
        if (head1.next == null && head2.next == null) {
            throw new RuntimeException("链表都为空链表无法合并~~");
        }
        //当当链表一为空时直接将单链表二挂在新链表的头节点
        if (head1.next == null) {
            head3.next = head2.next;
        } else {
            //链表一不为空时
            //将单链表一先挂到新的链表的头节点上
            head3.next = head1.next;
            //创建两个个辅助指针用于遍历单链表一与单链表二
            heroNode cur3 = head3;
            heroNode cur2 = head2.next;
            //创建一个next的值用于做取之后的后一个节点的保留
            heroNode next;
            //单链表二
            while (cur2 != null) {
                //说明新链表被遍历完了，单链表二中的节点全是比单链表中的大
                if (cur3.next == null) {
                    cur3.next = cur2;
                    break;
                }
                //将节点插入链表中
                if (cur2.no <= cur3.next.no) {
                    next = cur2.next;
                    cur2.next = cur3.next;
                    cur3.next = cur2;
                    cur2 = next;
                }
                cur3 = cur3.next;
            }
        }
        return NewSingleLinkedList;
    }
}
